Rodney Dugue đến từ báo The Village Voice cho rằng "Rehab" là một trong những bài hát nổi trội nhất trong album Good Girl Gone Bad,[27] trong khi nhà phê bình Sarah Rodman từ báo The Boston Globe đã gọi bài hát này là bài hát quan trọng nhất của album.[28] Quentin B. Huff từ tạp chí PopMatters đã gọi bài hát là "viên ngọc tí hon"[24] và đã so sánh bài hát với đĩa đơn "Take a Bow" năm 1994 của nữ ca sĩ Madonna hợp tác với Babyface.[24] Tạp chí Billboard đã nhận xét rằng bài hát là một bài hát nổi bật trong album, với "phần bè uyển chuyển của Timberlake, phần sản xuất căng tràn, và sự đối lập giữa giai điệu của nhạc cụ dây và guitar."[29] Shanel Odum từ tạp chí Vibe đã nhận thấy rằng phần lớn album bao gồm những bài hát có nhịp độ cao, vì thế nên những bản ballad trong album dần trở thành điểm yếu của nó, nhưng rốt cuộc lại được "cứu vớt" bởi chính "Rehab".[30] Spence D. từ IGN đã khẳng định rằng Rihanna và Timberlake là một cặp đôi tâm đầu ý hợp, tất cả là nhờ quãng âm tương đồng trong giọng hát của họ. Nhà phê bình còn viết thêm rằng bài hát "đã quay trở lại với một giai điệu nhạc R&B phong cách cũ của Rihanna, một tiết tấu được xây dựng bởi những tiếng rung lắc của trống lục lạc và những tiếng gảy của đàn guitar nhạc acoustic cùng với một nhịp sau được sắp xếp khôn khéo trong bài hát."[22] Doug Rule của tạp chí Metro Weekly đã miêu tả bài hát là "mang tính đặc trưng và hấp dẫn, tuy nhiên tính tương đồng giữa ca khúc và một số nhạc phẩm xuất sắc nhất của Timberlake là điều không thể nhầm lẫn được",[25] trong khi Sylvia Patterson từ báo The Guardian lại ví "Rehab" là một "câu chuyện về tình yêu bị thất lạc đầy sầu bi".[31]

Tom Breinan từ trang web Pitchfork Media đã nhận xét rằng Rihanna "đã tiến gần hơn trong việc khắc họa một thứ giống như cảm xúc con người, nhưng cô vẫn được giọng hát giống như một con robot được lập trình để đóng giả một Alanis Morissette." Neil Drumming từ Entertainment Weekly miêu tả ca khúc là một "liều chính kịch âm hưởng có một nhịp độ vừa phải đem lai nỗi buồn được dùng quá liều". Sal Cinquemani từ tạp chí Slant Magazine đã cho rằng "Rehab" đã chứng tỏ được "khả năng tuyệt vời của Timberlake trong việc sáng tác lời của các bài hát liên quan đến những cái mông khêu gợi hoặc những 'cái ấy' nằm trong hộp"—ám chỉ đến các đĩa đơn năm 2006 của Timberlake gồm "SexyBack" và "Dick in a Box".